package com.jxb.e20241230;

import java.util.Arrays;

public class HeapSort1 {

    public static void main(String[] args) {
        int[] nums = {1,3,5,3,9,4};
        sortArray(nums);
        System.out.println(nums);
    }

    static int len;

    public static int[] sortArray(int[] nums) {
        len = nums.length;
        if (len <= 0) {
            return nums;
        }

        //调整为最大堆
        adjustMaxHeap(nums);

        //调换堆顶元素和堆尾元素
        while (len > 0) {
            swap(nums,0,len-1);
            len--;
            //调整堆
            adjustHeap(nums,0);
        }
        return nums;
    }

    private static void adjustMaxHeap(int[] nums) {
        //从非叶子节点进行调整
        for (int i = (nums.length - 1)/2;i>=0;i--) {
            adjustHeap(nums,i);
        }
    }

    private static void adjustHeap(int[] nums, int i) {
        int maxIndex = i;
        int left = 2*i + 1;
        int right = 2*(i+1);
        if (left < len && nums[left] > nums[maxIndex]) {
            maxIndex = left;
        }
        if (right < len && nums[right] > nums[maxIndex] && nums[right] > nums[left]) {
            maxIndex = right;
        }
        if (i != maxIndex) {
            //将最大元素与左子树或者右子树进行替换
            swap(nums, maxIndex, i);
            adjustHeap(nums,maxIndex);
        }

    }


    private static void swap(int[] nums, int maxIndex, int i) {
        int temp = nums[maxIndex];
        nums[maxIndex] = nums[i];
        nums[i] = temp;
        System.out.println("经过一次调整的数组："+ Arrays.toString(nums));
    }

//    private static void swap(int maxIndex, int i, int[] nums) {
//        int temp = nums[maxIndex];
//        nums[maxIndex] = nums[i];
//        nums[i] = temp;
//    }

}
